perm filename UCSC[1,JRA] blob
sn#603994 filedate 1981-08-01 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00008 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 GET LARGE LISP EXAMPLES, EG STUFF IN BAXK OF PRIMER
C00004 00003 LISP
C00037 00004 Tuesday July 7, 1981
C00061 00005 Wednesday July 8, 1981
C00063 00006 Thursday, July 9, 1981
C00068 00007 Friday July 10, 1981
C00071 00008 title: LISP
C00074 ENDMK
C⊗;
GET LARGE LISP EXAMPLES, EG STUFF IN BAXK OF PRIMER
make slide of lending lib stuff
--------------------------------------------
my sched:
5-8am prep
8-8:30 drive
class 9am-10pm
home 11pm
set up "lending lib"
AUG BYTE
fpp
lispm manual
tlc manual
lisp conf proc
anatomy
mit ai 2-vol
ai handbook
winston lisp, ai
ai techniques
art of the interpreter
interlisp manuals
820/INCH WORM
********************************************
To do: slides
copy
racks paper
wand paper
flesh and bones
art of interp.(?)
bibliography suggestions
have tlc-lisp with editor available on trs-80 in red's office
... and bring to class
include examples of "reasonable" and "ugly" code
include errata on AIP, and list of losing hacks!
LISP
SESSION SCHEDULE
0. 7:00 - 9:00 Student's reading time!!
1. 9:00 - 10:30
2. 10:45 - 12:15
Lunch 12:30 1:30 (QA 1:00 - 1:30)
3. 1:30 - 3:00
4. 3:15 - 5:00
Dinner 5:00 - 7:00 (QA 6:00 - 7:00)
5. 7:00 - 10:00
Wednesday evening: Party
Monday July 6, 1981
--MORNING--
SESSION 1. 9:00 - 10:30
Introduction and Overview of Course
A Semi implementation-independent approach to LISP
If you understand the issues, you can map between dialects.
The LISP Language: Its History and Applications
Short History
LISP Tree from 704 to Date
In the Beginning was the 704...
BBN PDP-1 → SDS940 → PDP-6 → Interlisp-∞
MIT PDP-6 → Stanford → UCI → Rutgers
→ MIT Bibop → LispM → NIL
→ Franz LISP
VLISP PDP-10, PDP-11, micros
Standard LISP
Micro LISPs
VLISP, MU-LISP, TLC-LISP
Applications
Mathematical Theory of Computation
Program Proving
Computational Formalism
Semantics of Languages
Artificial Intelligence
Symbolic Mathematics
Macsyma
Reduce
Expert Systems
Data Bases
Natural Language
Searching
Systems Design
VLSI-CAD
LISP machine
Scheme Chip
The LISP Language: Its Rationale
For debugging ideas
Complex exploratory programming
Flexibility
High-level assembly language
von Neumann Graph-machine
Contemporary LISP: general purpose language
A systems implementation language, not an AI language
The LISP Language: Its Data
Data Structures: two categories of objects
atomic and composite objects.
Literals: The Identifiers (syntax items of most languages)
are data items in LISP.
As Symbols: Names
Guaranteed Names: ABC, A13, CAR, ...
Local Pathologies: FOO_2, %XY, foo, +, *, 1+
upper-case≠lower-case: CAR ≠ car
(see Appendix 1, "LISP" Winston & Horn)
As Collectors of Properties: Property Lists
Examples:
Symbol: BALL-22
properties values
DIAMETER 22
COLOR RED
LOCATION ROOM-14
Symbol: ROOM-14
properties values
LONGITUDE 135 DEGREE 19 MINUTE
LATITUDE 34 DEGREE 22 MINUTE
(Question: how to represent DEGREE and MINUTE information)
Representation of P-List:
Flexible Record Structure
Representation of Symbol:
Fixed-length block
value, property-list, and print-name
Numbers:
Integers
123, +123, -12345
Floating Point
123.5, 123.2E+10
Arbitrary Precision: fixed- and floating-point
Representations
Variable-length Blocks
Booleans
T, NIL
Representation: non-NIL for true
Lists
(A T CAR), ( ), (A (T (CAR 34) 22))
Representation: as dotted pairs with NIL terminator.
Dotted-pairs
(A . B) (A . NIL)
Representation: linked blocks of length two
typed pointers
N.B. the combined class of atoms, and dotted pairs is known
as Symbolic Expressions.
Vectors and Arrays
Representation: dope vector plus storage
Strings
"This is a String (with a parenthetical remark)"
Representation
Strings: fixed-length descriptors referencing variable-length
character strings.
Functions
As Passive Data: the LISP list-notation
(DEF F (X) (IF (= X 0)
1
(* X
(F (1- X)))))
As active data: functional objects --arguments and values
Representation
Primitives: as micro-code
user-defined: as lists
Local Pathologies
Hash Arrays
Hunks
dis-embodied P-lists
(compare with association-lists)
A Rationale for Programs as Data
Describing program manipulation systems
editors, compilers, debuggers, transformers
Syntax as a non-issue
The Notion of First-Class Objects: THE Issue in Data Structures
Can objects be:
Passed as Parameters?
Returned as Values?
Input as Constants?
Output as Values?
Assigned as Values?
SESSION 2. 10:45-12:15
The LISP language: active part
Comment conventions
~... <cr> in AIP
;... <cr> in MACLISP
(* ... ) in Interlisp
Applicative LISP: a value-oriented subset
Functional Style
(<function> <argument-1> <argument-2> ... <argument-n>)
Example: (F 1 3)
Composition of functions
(<function> (<function> <argument> ...) ...)
Example: (F (G 1) 3)
The Evaluation of Arguments: Call-By-Value
An Alternative: Call-by-Name
Ramifications of calling style:
Implicit control structure
Computation as Deduction plus Control
Deduction: axioms and rules of inference
Simplification and substitution rules
Control: strategies for applying rules
Substitute before simplify: Call-by-name
Simplify before substitute: Call-by-value
A Rarified System: The Lambda Calculus
A basis for pure LISP
A Representation for Constants
Use versus Mention
Meta-language versus Object-language
meta-language is object-language: a "Strange loop" (GEB)
use: Chicago is a city
mention: "Chicago" is a seven-letter word
use: ...(G 1) ...
mention: ...'(G 1) ...
'<s-expression> is an abbreviation for (QUOTE <sexpression>)
Primitive Operations on Data Structures
Predicates: Boolean-valued Functions
Equality: to tell if two objects are the "same" object
EQ: "same" as identity
(EQ 'A 'A) => T
(EQ NIL T) => NIL
(EQ X X) => T
(EQ (EQ 1 'A) NIL) => T
(EQ '(EQ 1 'A) NIL) => NIL
EQUAL: "same" as structurally equivalent
(EQUAL (CONS 1 3) (CONS 1 3)) => T
but typically not EQ!
(EQUAL 2 2) => T
but often not EQ!
(Interlisp has EQP for numeric equality)
Recognizers: to tell the "type" of a data object.
(NUMBERP <obj>)
(ATOM <obj>)
(NULL <obj>) return NIL if <obj> fails test
(LISTP <obj>)
(STRINGP <obj>)
(ARRAYP <obj>)
...
User-defined types
Interlisp, Maclisp, MDL
Numerical Operations: typical selection
addition, subtraction, ...
Example: arbitrary number of arguments
(PLUS <n> <n> ... <n>)
probably transcendentals, etc.
Example:
(ATAN x y) is an angle α such that x = r sin α,
and y = r cos α, for some r.
Lists, symbols, and dotted-pairs
Constructors: to construct new objects
Examples:
(LIST 1 3 5) => (1 3 5)
(LIST 1 (LIST 4 5) 5) => (1 (4 5) 5)
(CONS '(A B) 3) => ((A B) . 3)
Selectors: to extract components from composite data structures
Examples:
(CAR '(1 3)) => 1
(CDR (CDR '(1 3))) => ( ) [ ( ) ≡ NIL]
CAR-CDR chains: to be used sparingly
For li either A or D, the composition:
(Cl1 R (Cl2 R ...(Cln R <expression>)...) may be abbreviated as:
(Cl1 l2 ...ln R <expression>).
Example: (CADDR X) ≡ (CAR (CDR (CDR X)))
Arrays and Vectors
Interlisp examples:
(ARRAY n p v) n number slots, and pointer slots (initialized to v)
(ARRAYSIZE <obj>) gives size of <obj> if <obj> is an array
(ELT a n) gives a[n], and (SETA a n v) is a[n]←v
MACLISP comparisons:
(ARRAY <name> ...)
(a n) gives element a[n], and (STORE a n v) is a[n]←v
Notes: ARRAY in Interlisp generates an array object (which could
be used freely as a value; in Maclisp, ARRAY generates a
named object, not a pure value. Recall our discussion of
first-classness!
Strings
constructors, selectors, recognizers, and modifiers tend to be
very dialect-dependent
Conditional Expressions: explicit control structure
Simple Conditional
(COND (<predicate-1> <expression-1>)
(<predicate-2> <expression-2>)
... ...
(<predicate-n> <expression-n>))
Points: order-dependent semantics
fall-through value is NIL (in most implementations)
Example:
(COND ((NULL (CDR X)) (CONS 1 X))
((ATOM Y) (FUN (CONS 1 Y) X)))
Extended Conditional expressions
(COND (<predicate-1> <expression-1-1> <expression-1-2> ...)
(<predicate-2> <expression-2-1> <expression-2-2> ...)
... ...
(<predicate-n> <expression-n-1> <expression-n-2> ...))
Note: useful only with side-effects
Variations
(IF <predicate> THEN <true-expressions> ELSE <false-expressions>)
Example:
(IF (NULL (CDR X)) THEN (CAR Y) ELSE (CONS X Y))
Abbreviations
(COND (<predicate-1> <expression-1>)
(<predicate-2> <expression-2>)
... ...
(T <expression-n>))
(COND (<predicate-1> <expression-1>)
...
(<expression-i>)
... ...
(<predicate-n> <expression-n>))
SELECT and CASE
Defining functions
Using Names DE, DEFUN, DEFINE, DEFINEQ
(DE F (X) (COND ((EQ X 0) 1) ; Maclisp
(T (TIMES X
(F (SUB1 X))))))
(DEFINEQ F (LAMBDA (X)
(COND ((EQ X 0) 1) (* Interlisp style)
(T (TIMES X
(F (SUB1 X)))))))
LAMBDA: a.k.a PROC
Components of Functionality
Formal Parameters
Expression Body
(actually one more)
How it's Done: The Function-cell Problem
The single value-cell problem/solution
Anonymously
How
A functional object is (typically) a constant; thus
a name is excess baggage. Compare (PLUS 1 2) versus
(PLUS X Y) where X names a constant 1, and Y names
constant 1.
Example:
(LAMBDA (X Y)(CONS (CAR Y)(CADR X))) is a functional object.
To apply it, write:
((LAMBDA (X Y)(CONS (CAR Y)(CADR X))) '(A B) '(1 2)) for example.
Value is result of evlauating (CONS (CAR '(1 2))
(CADR '(A B))) , i.e. (1 . B)
A warning: Recursive definitions
(LAMBDA (X) (IF (EQUAL X 0) 1 (TIMES X (F SUB1 X))))
is NOT the factorial function. F must refer to that LAMBDA-expression.
Why Anonymous Functions?
Locality of Reference
Computational Benefit: Call-By-Value
((LAMBDA (X) ... X ... X ... X ... ) (EXPENSIVE_COMPUTATION Y))
An abbreviation: LET-expressions
(LET (X (EXPENSIVE_COMPUTATION Y)) ... X ... X ... X ...)
Three dirty corners: function-cell/value-cell
functional objects = ?
variable scoping: when?
(DE f (<vars>) <body>) as approximately:
(SETQ f (LAMBDA (<vars>) <body>)) or more likely:
(SETQ f '(LAMBDA (<vars>) <body>)) or,
(SETQ f (FUNCTION (LAMBDA (<vars>) <body>))) or,
(SETF f ↑-one of the above-↑)
Free Variables: a first mention.
((LAMBDA (X) (PLUS X Y)) 2)
Y is a free variable
Summary:
Data Structures represent abstract objects
Atomic objects are taken to be indivisible
Composite objects have fine structure, extracted by selector
functions. Composite objects are constructed by constructor functions.
All objects may be tested for their type, using recognizer functions.
Functional Programming language
computation represented by function application, composition of forms
control represented by conditional expressions.
definition by recursion.
--AFTERNOON--
--------------------------------------------
*********************************
*make slide of lending lib stuff*
*********************************
session 3 oveview
Examples of recursive definitions
Numeric Examples
Non-numeric Examples
Error conditions: who handles them, and how.
A special example: EVAL
--------------------------------------------
session 3
Examples of recursive definitions
Recursion is like induction:
Find the object to decompose
Extablish the termination case
Write the general case assuming that you have the result
for "lesser" objects.
numeric: "lesser" usually means "closer to zero"
lists: "lesser" usually means "closer to ( )"
S-exprs: "lesser" usually means "closer to atomic"
in general: "lesser" usually means "closer to primitive objects"
*** num sl***
*** non-num sl ***
Error conditions: who handles them, and how.
ERRORSET and ERROR: Interlisp
ERRSET and ERR: Maclisp
See CATCH and THROW
*** err sl***
A special example: EVAL
How to make data into program
EVAL-APPLY as a universal function
(EVAL <obj> {<env>}) where <obj> represents a LISP expression
***eval sl***
--------------------------------------------
session 4
Representation and Abstraction
Examples of their Interplay
Important to extract details out of algorithm
*** sqrt ex**
Important to match the representation to the
kinds of operations to be performed
***rat sl **
May even utilize multiple representation in the same problem.
*** comp sl **
add and substract: rectangular coordinates (x = Re[x]+j*Im[z])
multiply and divide: polar coordinates (z = Mag[z]*e↑j*Ang[z])
clean interface
algorithms can determine the type of the objects.
--------------------------------------------
session 5 overview
running on machine
--------------------------------------------
session 5
--------------------------------------------
SESSION 3
Examples of recursive definitions
Recursion is like induction:
Find the object to decompose
Extablish the termination case
Write the general case assuming that you have the result
for "lesser" objects.
numeric: "lesser" usually means "closer to zero"
lists: "lesser" usually means "closer to ( )"
S-exprs: "lesser" usually means "closer to atomic"
in general: "lesser" usually means "closer to primitive objects"
Numeric Examples
*** num sl
factorial in several styles
(DE FACT (X) (COND ((EQ X 0) 1)
(T (TIMES X (FACT (SUB1 X))))))
(DE FACT (X) (FACT1 (SUB1 X) X))
(DE FACT1 (X N)
(COND ((EQ X 0) 1)
(T (FACT1 (SUB1 X) (TIMES X N)))))
(DE FACT (X &OPTIONAL (N 1)) ;LISP machine style
(COND ((EQ X 0) 1)
(T (FACT (SUB1 X) (TIMES X N)))))
N.B. all parameters are "optional" in Interlisp; un-supplied
arguments default to NIL values.
*** num end
** non-num sl
Non-numeric Examples
example rationale
EQUAL to show a recursive predicate
(DE EQUAL (X Y)
(COND ((EQ X Y))
((AND (LISTP X) (LISTP Y))
(COND ((EQUAL (CAR X)(CAR Y))
(EQUAL (CDR X)(CDR Y)))
(T NIL)))
((AND (NUMBERP X) (NUMBERP Y))
(EQN X Y))
...))
MEMBER to show use of NIL/non-NIL truth values
(DE MEMBER (X L)
(COND ((NULL L) ( ))
((EQUAL X (CAR L)) L)
(T (MEMBER X (CDR L)))))
APPEND to show a simple contruction function
(DE APPEND (L1 L2)
(COND ((NULL L1) L2)
(T (CONS (CAR L1)
(APPEND (CDR L1) L2)))))
REVERSE to show a tricky construction
(DE REVERSE (L) (REV1 L ( ))
(DE REV1 (L1 L2)
(COND ((NULL L1) L2)
(T (REV1 (CDR L1)
(CONS (CAR L1) L2)))))
SUBST to show a tree construction
(DE SUBST (X Y Z)
(COND ((ATOM Z) (COND ((EQ Y Z) X) (T Z)))
(T (CONS (SUBST X Y (CAR Z))
(SUBST X Y (CDR Z))))))
COUNTATOMS to show a list computation
(DE COUNTATOMS (L)
(COND ((NULL L) 0)
((ATOM (CAR L)) (ADD1 (COUNTATOMS (CDR L))))
(T (PLUS (COUNTATOMS (CAR L))
(COUNTATOMS (CDR L))))))
**end non-num
Error conditions: who handles them, and how.
ERRORSET and ERROR: Interlisp
ERRSET and ERR: Maclisp
See CATCH and THROW
**err sl
** err end
A special example: EVAL
How to make data into program
EVAL-APPLY as a universal function
(EVAL <obj> {<env>}) where <obj> represents a LISP expression
<env> represents a symbol table
Example:
**eval sl
(EVAL (CONS 'CONS '(1 3)) NIL) => (1 . 3)
**end eval
SESSION 4
lots of examples: SQRT, rational and complex arithmetic courtesy
of Gerry Sussman.
***srt sl
(DE SQRT-ITER (PROPOSAL RADICAND)
(COND ((CLOSE-ENOUGH? PROPOSAL RADICAND) PROPOSAL)
(T (SQRT-ITER (IMPROVE PROPOSAL RADICAND) RADICAND))))
(DE IMPROVE (PROP RAD)
(AVERAGE PROP (QUOTIENT RAD PROP)))
(DE AVERAGE (X Y) (QUOTIENT (PLUS X Y) 2))
(DE CLOSE-ENOUGH (PROP RAD)
(LESSP (ABS (MINUS (SQUARE PROP) RAD)) 0.001))
(DE SQRT (NUMBER)(SQRT-ITER 1 NUMBER))
***sqrt end
----------------------Rational Arithmetic----------------------
***rat sl**
For this example, we have, for X representing a rational number:
(NUMER X) = N , (DENOM X) = D, and (MAKE-RAT N D) = X.
and we can define the rational arithmetic operations, eg rational multiplication:
(DE *RAT (X Y)
(MAKE-RAT (PLUS (NUMER X)(NUMER Y))
(PLUS (DENOM X)(DENOM Y)))), etc.
(DE =RAT (X Y)
(AND (EQUAL (NUMER X)(NUMER Y))
(EQUAL (DENOM X)(DENOM Y)))), will work provided we reduce to "lowest terms".
This can be done, either when we make rationals, or when we extract components.
For example, when making rationals:
(DE MAK-RAT (N D) (DE MAK-RAT-P (N D)
(IF (LESSP D 0) (LET (G (GCD (ABS N) D))
THEN (MK-RAT-P (MINUS N) (MINUS D)) (LIST (QUOTIENT N G)
ELSE (MK-RAT-P N D))) (QUOTIENT D Q))))
(DE NUMER (Q)(CAR Q)) (DE DENOM (Q)(CADR Q))
or when accessing components:
(DE MAK-RAT (N D)
(IF (LESSP D 0)
THEN (LIST (MINUS N)(MINUS D))
ELSE (LIST N D)))
(DE NUMER (Q) (DE DENOM (Q)
(LET (G (GCD (ABS (CAR Q)) (LET (G (GCD (ABS (CAR Q))
(CADR Q))) (CADR Q)))
(QUOTIENT (CAR Q) G))) (QUOTIENT (CADR Q) G)))
***end rat
Note: the representation we pick is a simple list: (<num> <denom>)
But more importantly, the algorithms that deal with the rational
arithmetic do not involve details of the representation. The interface
between the abstraction (rational numbers) and the implementation (LISP
lists) is clean.
----------------------Complex Numbers----------------------
In the previous example, we used two representations, essentially
independently. In the domain of complex numbers, tere are benefits in
choosing different representations, based on the operations to be
performed: rectangular form (x = Re[x]+j*Im[z]) is most convenient for
addition and subtraction, while polar form (z = Mag[z]*e↑j*Ang[z]) is
appropriate for multiplication and division.
We specify abstract selectors: REAL-PART, IMAG-PART, MAGNITUDE, and ANGLE
with the appropriate properties:
***comp sl
(MAKE-RECTANGLE (REAL-PART X)(IMAG-PART X)) = X
(MAKE-POLAR (MAGNITUDE Z) (ANGLE Z)) = Z
(DE +C (Z1 Z2)
(MAKE-RECTANGULAR (PLUS (REAL-PART Z1) (REAL-PART Z2))
(PLUS (IMAG-PART Z2) (IMAG-PART Z2))))
(DE *C (Z1 Z2)
(MAKE-POLAR (TIMES (MAGNITUDE Z1)(MAGNITUDE Z2))
(PLUS (ANGLE Z1) (ANGLE Z2))))
with appropriate definitions for -C and /C. Of course we now have to be a
bit more careful in choosing a representation: we have to be able to
distinguish between a "polar" representation and a "rectangular"
representation. We do this by including a "type tag", --RECTANGULAR or
POLAR-- in the representation:
(DE MAKE-RECTANGULAR (R I) (DE MAKE-POLAR(M A)
(LIST 'RECTANGULAR R I)) (LIST 'POLAR M A))
(DE RECTANGULAR? (Z) (DE POLAR? (Z)
(AND (NOT (ATOM Z)) (AND (NOT (ATOM Z))
(EQ (CAR Z) 'RECTANGULAR))) (EQ (CAR Z) 'POLAR)))
(DE REAL-PART (Z) (DE MAGNITUDE (Z)
(COND ((RECTANGULAR? Z) (CADR Z)) (COND ((RECTANGULAR? Z)
((POLAR? Z) (TIMES (CADR Z) (SQRT (PLUS (SQUARE (CADR Z))
(COS (CADDR Z))))) (SQUARE (CADDR Z)))))
((POLAR? Z) (CADR Z))))
(DE IMAG-PART (Z) (DE ANGLE (Z)
(COND ((RECTANGULAR? Z) (CADDR Z)) (COND ((RECTANGULAR? Z)
((POLAR? Z) (TIMES (CADR Z) (ATAN (CADDR Z) (CADR Z)))
(SIN (CADDR Z)))))) ((POLAR? Z) (CADDR Z))))
(where (ATAN x y) is an angle α such that x=r sin α, and y= r cos α, for some r.)
***end comp
--EVENING--
SESSION 5.
LMM How to Run on a Machine
READ-EVAL-PRINT
input/output
editing, debugging, compiling
Exercises and Short LISP Programs
Tuesday July 7, 1981
session 1 overview
Extensions of the Applicative Subset
Syntactic extensions
Macros
Run-Time
Read-Time
Semantic extensions
Special Forms
extended control structures
Mappers: functional arguments
Applications
Semantics: what IS a functional object
The "funarg problem"
--------------------------------------------
session 1
Other Function Types
Macros: Manipulating Expressions as Data
Run-time Macros: abbreviation and language extension
an extra evaluation cycle for macros
Why have macros?
abbreviation
representation-independence with compiled efficiency
Examples
IF
***if sl**
LET
*** let sl**
Read Macros
simple example
***qu sl**
Back-quote
Usefule for simplifying macro definitions
examples
**bq sl**
Read-tables and table-driven scanners: to redefine characters
Applications of Macros: Representation and Abstraction
Record Packages
Chapter 4 of AIP
The := Macro, AIP Section 9.2
(:= target value) hides the "type" of target
Special Forms: to extend the control structure
Call-unevaluated
***sf sl
Why have Special forms?
Problems with Special Forms
evaluation of text
Recursive simulation of iteration
Functional Arguments: Mapping Functions
Specific examples:
***fn sl
dialectial issue: (LAMBDA ...) vs (QUOTE (LAMBDA ... ))
vs (FUNCTION (LAMBDA ...))
Generalized mappers:
***map sl
AIP Collectors as Macros on Functionals: AIP, Sections 5.6-5.9
*** for sl
Scoping rules:
Dynamic Scoping: latest binding
Static Scoping: lexical scoping
*** sco sl
Tail Recursion
iterative execution of recursive functions
an interpreter "optimization"
*** tail sl
--------------------------------------------
session 2 overview
Imperative lisp: an effect-oriented subset
Side-effects
Iteration
structured
primeval PROGs
Property-lists
Association lists
Data-driven programming
--------------------------------------------
session 2
Imperative lisp: an effect-oriented subset
Side-effects
Assignment expressions
**ass sl
Input-Output
READ and PRINT
** ??**
Iteration
structured
looping constructs
MACLISP-DO and Other Structured Iteration
**do sl
PROG: the primeval construct
**prog sl
"PROG variables" - local variables
PROG body
sequence of expressions
(RETURN <expression>)
(GO <label>) - label pairs
Example:
CATCH-THROW pairs and RETFROM
**cat sl
Property-lists
The primitives p-list functions
** pl sl
View these functions as table-manipulating functions,
typically for sparse tables
A related notion: Association lists
**as sl
Applications
A Powerful Application: Data-driven Programming
Modularity and Abstraction
Decoupling representation from the notion
type dispatching
Examples:
Complex Arithmetic again
** comp sl
Chapter 9, AIP
--------------------------------------------
session 3 overview
The Programming Language, LISP: Structure Modification
The modification primitives
Applications
Examples
Chapters 7 & 10 AIP
Review of Full LISP: applicative + imperative + modification
Our presentation
AIP Chapter 1-10
Pitfalls, Idiosyncracies, and gotchas
--------------------------------------------
session 3
List Modification
Boxes-and-arrows: graphical notation
Useful primitives, useful functions:
(RPLACA <target> <value>): <target> is a CONS-cell; replace its
CAR slot with <value>; result is the modified CONS-cell.
(RPLACD <target> <value>): <target> is a CONS-cell; replace its
CDR slot with <value>; result is the modified CONS-cell.
NCONC: The destructive form of APPEND
** mod prim sl
Creation of complex list-structure.
Modification, rather than copying
Pitfalls: aliasing
An example
***mod ex
Chapters 7 & 10, AIP
Applications of data structure modification
editing
complex list structure
A suprise: RPLACA/D as functional objects
A mystery to be solved on Friday.
Review of Chapters 1-10 of AIP
Pitfalls, Idiosyncracies, and gotchas
--------------------------------------------
SESSION 4.
Abstraction and Representation
Record Packages
LMM Examples of complex structure building
Examples of complex programming
how to attack large problems
how about a discourse on a converging sequence of representations?
First Project
--------------------------------------------
--EVENING--
SESSION 5.
Discussion of Previous Night
Do First project
--------------------------------------------
--MORNING--
SESSION 1. 9:00 - 10:30
Other Function Types
Macros: Manipulating Expressions as Data
Run-time Macros: abbreviation and language extension
** mac sl
definition: (DM name (var) body)
call: (name args)
binding: var <= (name args)
(DM FIRST (L) (CONS 'CAR (CADR L)))
(FIRST '(A B C)) => A
** end mac
** if sl
The definition of IF: (IF p a b) ≡ (COND (p a) (T b))
LMM (DM IF (EXP)
WILL (LIST 'COND
DO! (LIST (CADR EXP) (CADDR EXP))
(CONS T (CDDDR EXP))))
** let sl
The definition of LET1:
(LET1 (var_1 val_1 ... var_n val_n) body)
≡ ((LAMBDA (var_1 ... var_n) body) val_1 ...val_n)
(DM LET (EXP)
(CONS (CONS 'LAMBDA
(CONS (ALTERNATE (CADR EXP))
(CDDR EXP)))
(ALTERNATE (CDR (CADR EXP)))))
(DE ALTERNATE (L) (COND ((NULL L) ( )
((NULL (CDR L)) L)
(T (CONS (CAR L)
(ALTERNATE (CDDR L))))))
**end let
**qu sl
Read Macros
' as QUOTE
(DRM \' () (LIST (QUOTE QUOTE) (READ)))
< e1 e2 ... en > as (LIST e1 e2 ... en)
**end qu sl
**bq sl
Back-quote
Section 3.3, AIP
|" begin back quote (called such because MacLISP uses ` )
|@ splice in result (MacLISP uses ,@)
@ CONS in result (MacLISP uses ,)
a short example: let A be the list (1 2 3), then
|"(A @A) => (A (1 2 3))
|"(A |@A) => (A 1 2 3)
(DM IF (EXP)
|"(COND (@(CADR EXP) @(CADDR EXP))
(T @(CDDDR EXP))))
(DM LET (EXP)
|"(LAMBDA @(ALTERNATE (CADR EXP))
@(CDDR EXP)))
@(ALTERNATE (CDR (CADR EXP)))))
**end bq
Read-tables and table-driven scanners: to redefine characters
Applications of Macros: Representation and Abstraction
Record Packages
Chapter 4 of AIP
The := Macro, AIP Section 9.2
Special Forms: to extend the control structure
Call-unevaluated
Problems with Special Forms
** sf sl
definition: (DF name (var) body) (dialect dependent)
call: (name . args)
binding: var <= args
(DF F (L) L)
(DEFUN F FEXPR (L) L)
interlisp?
(F 1 2 (CONS 1 2)) => (1 2 (CONS 1 2))
**end sf sl
Imperative LISP: an effect-oriented subset
Recursive simulation
Functional Arguments: Mapping Functions
Specific examples:
***fn sl**
(DE INCR (L) (IF (NULL L)
( )
(CONS (ADD1 (CAR L))
(INCR (CDR L)))))
(DE INC (F L) (IF (NULL L)
( )
(CONS (F (CAR L))
(INC F (CDR L)))))
(DE INCR (L) (INC '(LAMBDA (X) (PLUS N X)) L))
** end fn
dialectial issue: (LAMBDA ...) vs (QUOTE (LAMBDA ... ))
vs (FUNCTION (LAMBDA ...))
Generalized mappers:
** map sl
(DE MAPCAR (FN L) (IF (NULL L)
( )
(CONS (FN (CAR L))
(MAPCAR FN (CDR L)))))
(DE MAPLIST (FN L) (IF (NULL L)
( )
(CONS (FN L)
(MAPLIST FN (CDR L)))))
(DE MAPC (FN L) (IF (NULL L)
( )
(FN (CAR L)
(MAPC FN (CDR L))))
(DE MAP (FN L) (IF (NULL L)
( )
(FN L)
(MAP FN (CDR L))))
(DE MAPCAN (FN L) (IF (NULL L)
( )
(NCONC (FN (CAR L))
(MAPCAN FN (CDR L)))))
-- NCONC will be discussed this afternoon --
(DE MAPCON (FN L) (IF (NULL L)
( )
(NCONC (FN L)
(MAPCON FN (CDR L)))))
** end map
**for sl
AIP Collectors as Macros on Functionals: AIP, Sections 5.6-5.9
(FOR -(variable IN list)-
(WHEN exp1)
(DO | SAVE | FILTER | SPLICE exp2))
DO: no results saved
SAVE: list of the results is returned
FILTER: list of all non-NIL results is returned
SPLICE: "flattened list", list formed by applying NCONC, is returned
Translations
(FOR (X IN L) (SPLICE (FOO X))) ≡ (MAPCAN 'FOO L)
(FOR (X IN L) (SAVE (FOO X))) ≡ (MAPCAR 'FOO L)
(FOR (X IN L) (FILTER (FOO X)))
≡ (MAPCAN '(LAMBDA (X) (LET (X (FOO X))
(IF X
THEN (LIST X)
ELSE X)))
L)
(FOR (X IN L) (DO (FOO X))) ≡ (MAPC 'FOO L)
Examples: (see page 150 AIP)
(FOR (ANS IN '((A B) (C D)))
(SAVE (APPEND ANS '(1 2 3))))
≡ ((A B 1 2 3) (C D 1 2 3))
(FOR (SUB IN (UNIFY IMP A))
(SPLICE (FOR (ANS IN (RETRIEVE SUB))
(SAVE (APPEND ANS SUB)))))
≡ (MAPCAN '(LAMBDA (SUB)
(MAPCAR '(LAMBDA (ANS) (APPEND ANS SUB))
(RETRIEVE SUB))
(UNIFY IMP A))
**end for
Scoping rules:
**sco sl
(DE TEST (L)
(MAPCAR '(LAMBDA(X)(CONS X L)) '(1 2 3 4)))
(TEST '(A B C))
... evaluate (FN (CAR L)) where FN: (LAMBDA (X) (CONS X L))
L: (1 2 3 4)
... evaluate (CONS X L) where X: 1
L: ?
Dynamic Scoping: latest binding
Static Scoping: lexical scoping
** end sco
**tail sl
Tail Recursion
(DE FACT (N) (FAC1 N 1)
(DE FAC1 (N M) (IF (EQUAL N 1)
M
(FAC1 (SUB1 N) (TIMES N M))))
executed like:
(DE FAC1(N M)
INTERNAL-FAC1 (TEST (EQUAL N 1)
M
(PAR-ASSIGN N (SUB1 N)
M (TIMES N M))))
(JUMP INTERNAL-FACT1))
**end tail
SESSION 2. 10:45-12:15
Side-effects
Assignment Expressions
**ass sl
SETQ
(SETQ X 2)
SET
(SETQ X 2) ≡ (SET 'X 2)
**ass sl
READ and PRINT
MACLISP-DO and Other Structured Iteration
** do sl
(DO (-(var_i init_exp iter_exp)-)
(end_test end_val)
-body-)
(DE FACT (N)
(DO ((M 1 (TIMES N M) (N N (SUB1 N)))
((= N 1) M)))
(DE SIMP-COUNTATOMS (L)
(DO ((L L(CDR L))
(COUNT 0 (ADD1 COUNT)))
((NULL L) COUNT)))
Note: FOR packages up control on a list/sequence;
what about a control construct that packages
control on a tree?
** end do
PROG: the primeval construct
** prog sl
"PROG variables" - local variables
PROG body
sequence of expressions
(RETURN <expression>)
(GO <label>) - label pairs
Example:
(DE FACT (N)
(PROG (M)
(SETQ M 1)
L (COND ((= N 1) (RETURN M)))
(SETQ M (TIMES M N))
(SETQ N (SUB1 N))
(GO L)))
** end prog
** cat sl
CATCH-THROW pairs and RETFROM
"non-structured" control structures
(CATCH <label> <expression>)
(THROW <label> <expression>)
(RETFROM <label> <expression>)
labeled DOs in LISPM LISP
**end cat
* pl sl
Property-list Functions
(values computed often depend on implementation)
(PUTPROP <name> <indicator> <value>)
or
(PUTPROP <name> <value> <indicator>) ~ AIP
or
(PUT <name> <indicator> <value>) (* Interliap)
(GET <name> <value>)
(REMPROP <name> <value>)
(PLIST <name>)
**end pl
View these functions as table-manipulating functions,
typically for sparse tables
A related notion: Association lists
(ASSOC <symbol> <a-list>) returns the first pair whose key matches
<symbol>.
*** as sl
draw picture by hand
**** end sl
*** comp sl
(DE REAL-PART-RECTANGULAR (Z) (DE REAL-PART-POLAR (Z)
(CAR Z)) (* (CAR Z) (COS (CADR Z))))
... ...
(DE ANGLE-RECTANGLE (Z) (DE ANGLE-POLAR (Z)
(ATAN (CADR Z) (CAR Z))) (CADR Z))
and install these fragments on the appropriate property lists:
(PUTPROP 'RECTANGULAR 'REAL-PART REAL-PART-IMAGINARY)
... ...
(PUTPROP 'POLAR 'ANGLE ANGLE-POLAR)
Now we can (1) use the type information stored with each object
to (2) GETPROP the appropriate code fragment, and
(3) do a "type dispatch", applying that code segment to the object.
For example:
(DE REAL-PART (OBJ) (OPERATE 'REAL-PART OBJ))
where:
(DE OPERATE (OP OBJ)
(LET (PROC (GETPROP (TYPE OBJ) OP)))
(IF (NOT (EQ (PROC NIL)) ;Operator is/is-not defined on type
(PROC (REP OBJ)) ;apply PROC to OBJ
(ERROR "Operator not defined on this type"))))
(DE TYPE (OBJ) (CAR OBJ)) (DE REP (OBJ) (CDR OBJ))
**end sl
Data-Driven Programming: Chapter 9, AIP
--AFTERNOON--
SESSION 3.
List Modification
Boxes-and-arrows: graphical notation
Useful primitives, useful functions:
(RPLACA <target> <value>): <target> is a CONS-cell; replace its
CAR slot with <value>; result is the modified CONS-cell.
(RPLACD <target> <value>): <target> is a CONS-cell; replace its
CDR slot with <value>; result is the modified CONS-cell.
NCONC: The destructive form of APPEND
*** mod prim
(RPLACA '(A B) 1) => (1 B)
(RPLACD '(A B) 1) => (A . 1)
(NCONC '(A B) '(1 2 3)) => (A B 1 2 3)
***prim end
Creation of complex list-structure.
Modification, rather than copying
Pitfalls.
*** mod ex sl
(SETQ X '(A B C)) (* Make X a constant list)
(A B C)
(SETQ Y X) (* Share X)
(A B C)
(RPLACA Y 1) (* Smash the A)
(1 B C)
X (* The "constant" has been modified)
(1 B C)
(RPLACD (CDR Y) ()) (* A not-so-transparent modification)
(B)
X (* Further deterioration of X)
(1 B)
**end mod ex
Chapters 7 & 10, AIP
Applications of data structure modification
A suprise: RPLACA/D as functional objects
A mystery to be solved on Friday.
More examples of LISP programming
Review of Chapters 1-10 of AIP
Pitfalls, Idiosyncracies, and gotchas
SESSION 4.
Abstraction and Representation
Record Packages
LMM Examples of complex structure building
Examples of complex programming
how to attack large problems
how about a discourse on a converging sequence of representations?
First Project
--EVENING--
SESSION 5.
Discussion of Previous Night
Do First project
Wednesday July 8, 1981
--MORNING--
SESSION 1.
s1
Chapter 11 AIP
Simple discrimination nets
AI "Data" Bases
Planner/Conniver
Patterns
variables and constants
matching
Assertions: facts
Methods: virtual facts (procedures)
THECONSE/IF-NEEDED
Demons
THANTE/IF-ADDED,IF-REMOVED
High-level Structure
Goal-Directed
Pattern-directed Invocation
Backtracking
s2
Prolog: A logic programming language
A bridge between practice and theory
Computation as deduction plus control, again.
Chapter 13 AIP
Overview of logic
Propositional Calculus
Predicate Calculus
Mechanization of Deduction
Chaining
Pattern-matching and Unification
A Worked example
SESSION 2.
s3
Chapter 14 AIP
Discrimination Nets with Variables
Chapter 16 AIP
The Need for Justifications: responsible systems
Reasoning: non-monotonic logics
--AFTERNOON--
SESSION 3.
LMM More examples of AI applications
SESSION 4.
LMM Discuss project 1
Setup project 2
--EVENING--
SESSION 5.
Short session (7:00 - 8:30)
Party
Debate: lexical vs. dynamic scope
shallow vs. deep binding
Maclisp vs. Interlisp vs. Scheme
Thursday, July 9, 1981
--MORNING--
SESSION 1.
s1
Evaluation in LISP
AI as language design: LISP as a SIL
Planner, Conniver, etc.
Interpreter construction
LISP with constants
*** eval
*** apply
*** evlis
Symbol tables: The Simulation of Substitution
A representation: linked blocks
*** lookup/lookup1
*** mk-env
LISP with Variables
See EVAL above, sections marked ;$$$$
s2
LISP with functional objects: See ;***
Scoping Issues
Dynamic Scoping
Lexical Scoping
SCHEME
Functional objects: access as data
Going further: control as data
Continuations
CATCH and THROW
Applications
Multi-processing formalisms
Introspective systems
SESSION 2.
Implementation techniques
Data Representation: Storage Management
Storage layout
Typed-pointers
Bibop
Dynamic Memory and Garbage Collection
Reference counting
LMM Software
Hardware
Program Execution: The LISP Processor
Function Arguments and Values
LMM Deep and Shallow Binding
Spaghetti
Software
Hardware
--AFTERNOON--
SESSION 3.
Chapter 15, AIP
XRL: An Example of an AI language
Hierarchies and Flavors
Smalltalk
LISP Machine LISP
SESSION 4.
More project two
--EVENING--
SESSION 5.
Do Project two
--------------------------------------------
***eval s1a
(DE EVAL (X ENV)
(COND ((IS-CONST X) (VAL X))
((IS-VAR X) (LOOKUP X ENV)) ;$$$$$
((IS-IF X) (IF (EVAL (PREM X) ENV)
(EVAL (CONSE X) ENV)
(EVAL (ANTE X) ENV)))
((IS-LAMBDA X) (MK-PROCEDURE X ENV)) ;****
(T (APPLY (EVAL (FUN X) ENV)
(EVLIS (ARGS X) ENV)
ENV))))
***apply s1b
(DE APPLY (FN EARGS ENV)
(COND ((IS-PRIM FN) (DOIT FN EARGS))
((IS-PROCEDURE FN) (EVAL (BODY FN)
(MK-ENV (FORM FN) ;$$$$$
EARGS
(ENV FN)))) ;****
(T (ERROR "BAD OPERATOR -- APPLY"))))
***evlis s1c
(DE EVLIS (L ENV)
(IF (NULL L)
( )
(CONS (EVAL (FIRST L) ENV)
(EVLIS (REST L) ENV))))
***lookup/lookup1 s1d
The code for searching:
(DE LOOKUP (N ST)
(COND ((NULL ST) (ERROR "Unbound variable"))
(T (LOOKUP1 (NAMES (FIRST ST))
(VALUES (FIRST ST))
ST))))
(DE LOOKUP1 (N NAMES VALUES ST)
(COND ((MT-Y NAMES)(LOOKUP N (REST ST)))
((EQ N (GET-N NAMES))(GET-V VALUES))
(T (LOOKUP1 N
(TAIL NAMES)
(TAIL VALUES)
ST))))
***mk-env s1d
The code for construction:
(DE MK-ENV (FORM ACT ENV)
(LINK (BLOCK FORM ACT) ENV))
Friday July 10, 1981
--MORNING--
SESSION 1.
s1
Functionals and object-oriented programming
Funargs
The problem with dynamic scoping
Funvals: Lexically-scoped "LISP"
Message Passing Explained as Functionals
Packaging of function names
Function names as messages
The CONS example
Complex Arithmetic revisited
An extension of data-driven programming
Analysis: what's active (function)? what's passive (data)?
A numerical example
Hierarchies revisited
s1a
(DE CONS (X Y)
(LAMBD (MSG) (CASE MSG
(CAR X)
(CDR Y)
(RPLACA (LAMBDA (NEW-CAR) (SETQ X NEW-CAR)))
(RPLACD (LAMBDA (NEW-CDR) (SETQ Y NEW-CDR))))))
(DE CAR (X) (X 'CAR)) (DE RPLACA (X Y)((X 'RPLACA) Y))
etc.
s1b
(DE POLAR-COMPLEX (MAG ANG)
(LAMBDA (MSG) (CASE MSG
(REAL-PART (TIMES MAG (COS ANG)))
(IMAG-PART (TIMES MAG (SIN ANG)))
(MAGNITUDE MAG)
(ANGLE ANG))))
s1c
(DE RECTANGULAR-COMPLEX (REAL IMAG)
(LAMBDA (MSG) (CASE MSG
(REAL-PART REAL)
(IMAG-PART IMAG)
(MAGNITUDE (SQRT (PLUS (SQUARE REAL)
(SQUARE IMAG))))
(ANGLE (ATAN IMAG REAL)))))
and now we define: (DE REAL (OBJ) (OBJ 'REAL))
etc.
s1d
2 + 5
eval arguments
2 => 2
5 => 5
=> 7
active: +
passive: 2 5
s1d
2 + 5
send message "+" to object 2
2 <= "+"
=> message "2 + what"
(LAMBDA (X) (PLUS 2 X))
send message 5 to this object
5 <= (LAMBDA (X) (PLUS 2 X))
=> 7
active: 2
passive: +
active: 5
Is 7 active or passive?
SESSION 2.
John McCarthy: "Proving Correctness of LISP Programs"
--AFTERNOON--
SESSION 3.
More Applications
SESSION 4.
Discussion of Projects
Overview and Critique of the Course
title: LISP
LISP has been the major language of the Artificial Intelligence community
for over twenty years. Recently, many of these results have begun to find
commercial applications. These include:
⊗ medical diagnosis,
⊗ natural language understanding,
⊗ integrated circuit design,
⊗ genetic engeneering,
⊗ geological analysis.
Furthermore, LISP has been found valuable for the development and design
of complex software, like:
⊗ operating systems,
⊗ compilers,
⊗ text editors,
⊗ algebraic manipulation systems.
Finally, as a descriptive notation, LISP expedites the discussion and
understanding of topics like:
⊗ an abstract data structure view of programming;
⊗ an object-oriented view of computing as supported by Smalltalk;
⊗ a functional programming style as advocated by Backus;
This blend of theoretical elegance and practical pragmatics that underlie
the power of LISP will be presented in a way that leaves the student with
a solid grasp of both of these facets so that they can make informed
judgements about the language and its applicability to their problem
domain.
Specifically, the participants will obtain:
⊗ a thorough understanding of the language and its programming style.
⊗ a through grounding in the techniques of representation and
abstraction in Artificial Intelligence programming.
⊗ a hands-on familarity with interactive LISP tools.
For whom:
The course is designed for those expecting to do advanced LISP
applications. Prior experience with LISP is not required, but experience
in handling complex programming tasks may prove benificial.
Course materials:
class notes, Artificial Intelligence Programming, and Anatomy of LISP.